# -*- coding: utf-8 -*-

# __date:       2021/6/24
# __author:     Yang Chao
# __function:   Median of Two Sorted Arrays

from typing import List


class Solution:

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        解法一：
        创建辅助数组，将两个数组中的元素按照顺序加入数组，最终返回中间值即可
        时间复杂度（m + n）
        空间复杂度(m + n)
        """
        m = len(nums1)
        n = len(nums2)
        if m == 0 and n == 0:
            return
        c1, c2 = 0, 0
        arr = []
        while c1 < m or c2 < n:
            if c1 == m:
                arr.append(nums2[c2])
                c2 += 1
            elif c2 == n:
                arr.append(nums1[c1])
                c1 += 1
            elif nums1[c1] < nums2[c2]:
                arr.append(nums1[c1])
                c1 += 1
            else:
                arr.append(nums2[c2])
                c2 += 1
        if (m + n) & 1 == 1:
            return arr[(m + n) // 2]
        mid = (m + n) // 2
        return (arr[mid] + arr[mid - 1]) / 2

    def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
        """
        解法二：
        直接指针进行遍历，每次搜索当前数组中最小的元素，当两数组长度和为奇数时，搜索一半位置的数据记位中间值
        当两数组长度为偶数时，搜索一半位置及一半位置前一个元素和的一半即为中位数
        时间复杂度（（m+n）/2）
        """
        m = len(nums1)
        n = len(nums2)
        left, right = -1, -1
        c1, c2 = 0, 0
        for i in range((m + n) // 2 + 1):
            left = right
            if c1 >= m:
                right = nums2[c2]
                c2 += 1
            elif c2 >= n:
                right = nums1[c1]
                c1 += 1
            elif nums1[c1] < nums2[c2]:
                right = nums1[c1]
                c1 += 1
            else:
                right = nums2[c2]
                c2 += 1
        if (m + n) & 1 == 1:
            return right
        else:
            return (left + right) / 2

    def findMedianSortedArrays3(self, nums1: List[int], nums2: List[int]) -> float:
        """
        解法三：二分查找算法
        在两个数组中找出较短的数组长度进行二分遍历，由于中位数的性质，定好较短数据的分割点之后，另外一个数据的分割点相应的就可以确定
        找到分割点之后，检查当前的分割点是否满足可以找到中位数的条件，如果不满足，调整分割点，如果满足，则直接计算中位数
        时间复杂度(log (m+n))
        """
        m = len(nums1)
        n = len(nums2)

        def binary_search(arr1, arr2, m, n):
            m_left = 0
            m_right = m
            while(m_right <= m):
                i = (m_left + m_right) // 2
                j = (m + n) // 2 - i
                if i != 0 and j != n and arr1[i - 1] > arr2[j]:
                    m_right = i - 1
                elif j != 0 and i != m and arr2[j - 1] > arr1[i]:
                    m_left = i + 1
                else:
                    minRight = -1
                    if i == m:
                        minRight = arr2[j]
                    elif j == n:
                        minRight = arr1[i]
                    else:
                        minRight = min(arr1[i], arr2[j])
                    if (m + n) & 1 == 1:
                        return minRight
                    maxLeft = -1
                    if i == 0:
                        maxLeft = arr2[j - 1]
                    elif j == 0:
                        maxLeft = arr1[i - 1]
                    else:
                        maxLeft = max(arr1[i - 1], arr2[j - 1])
                    return (minRight + maxLeft) / 2

        if m > n:
            nums1, nums2 = nums2, nums1
            m, n = n, m
        return binary_search(nums1, nums2, m, n)

    def findMedianSortedArrays4(self, nums1: List[int], nums2: List[int]) -> float:
        """
        解法四：分治求最小k元素的思想(巨帅的思想)
        算法思路：当两个元素长度和为奇数时，求(m+n)//2 + 1个小值即可，而长度和为偶数时，则需要分别求(m+n)//2和(m+n)//2 + 1个小值，然后取均值
        找最小k值的思路：
            首先在两个数组中分别找k/2个小的元素，如果一个数组中的元素小于另外一个数组，则直接干掉当前数组前k/2个元素即可
        """
        m = len(nums1)
        n = len(nums2)

        def find_minK(k: int):
            c1, c2 = 0, 0
            while (k != 0):
                if c1 == m:
                    return nums2[c2 + k - 1]
                if c2 == n:
                    return nums1[c1 + k - 1]
                if k == 1:
                    return min(nums1[c1], nums2[c2])

                index1 = min(c1 + k // 2 - 1, m - 1)
                index2 = min(c2 + k // 2 - 1, n - 1)
                value1, value2 = nums1[index1], nums2[index2]

                if value1 <= value2:
                    k -= (index1 - c1 + 1)
                    c1 = index1 + 1
                else:
                    k -= (index2 - c2 + 1)
                    c2 = index2 + 1

        if (m + n) & 1 == 1:
            return find_minK((m + n + 1) // 2)
        return (find_minK((m + n) // 2) + find_minK((m + n + 2) // 2)) / 2

    def findMedianSortedArrays5(self, nums1: List[int], nums2: List[int]) -> float:
        """
        解法五：学习python语言机制， 数组可以直接相加合并
        """
        nums = nums1 + nums2
        nums.sort()
        length = len(nums)
        if length & 1 == 1:
            return nums[length // 2]
        return (nums[length // 2] + nums[length// 2 - 1]) / 2